package leetcode.list;

import utils.node.ListNode;

/**
 * DESCRIPTION: https://leetcode-cn.com/problems/reverse-linked-list/
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 * Author: ammar
 * Date:   2021/12/9
 * Time:   下午8:05
 */
public class _206_反转链表 {

    public static void main(String[] args) {
        ListNode head = Tools.generList(new Integer[]{1, 2, 3, 4, 5});
//        ListNode newhead = reverseListRecursion(head);
        ListNode newhead = reverseListIteration(head);
        System.out.println(newhead);
    }

    /**
     * 方法一：递归 1 2 3 4 5 -> 5 4 3 2 1
     *
     * @param head 节点1
     * @return
     */
    public static ListNode reverseListRecursion(ListNode head) {
        if (head == null) return head; // head 为空 直接返回空
        if (head.next == null) return head; // 链表只有一个元素 返回本身即可
        /**
         * 这句代码的意思是：
         * 把 2 传进来，然后链表变成了 5 4 3 2 <- 1
         * node 就是 5
         */
        ListNode second = head.next;
        ListNode five = reverseListRecursion(second);
        // 此时需要将 2 拿到，2 的 next 指向 1 并且，将 1 指向空
        second.next = head;
        head.next = null;
        return five;
    }

    /**
     * 方法二：非递归 迭代  1 2 3 4 5 -> 5 4 3 2 1
     * @param head
     * @return
     */
    public static ListNode reverseListIteration(ListNode head) {
        if (head == null) return head; // head 为空 直接返回空
        if (head.next == null) return head; // 链表只有一个元素 返回本身即可

        /**
         * new -> 1 (first) 2 (head) -> 3 (temp) -> 4 -> 5
         * new -> 2
         * 2 (head) -> 1 (first)
         * head = 3
         * 1 -> 3 4 5
         */
        ListNode newHead = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }
}